package Algorithm.sort.basic;

import java.util.Arrays;

/**
 * 算法思想：从第二个元素开始从前往后扫描，每扫描到一个元素，就将其插入到前面的序列使其构成有序序列，扫描完最后一个元素则整个序列有序
 *
 * 优化：插入时采用折半查找寻找插入位置，比较关键字的次数减少了，但是移动元素的次数没变，所以时间复杂度依然是O(n^2)
 *
 * 性能：时间复杂度平均O(n2)，最好O(n2)，最坏O(n2)。空间复杂度O(1)。稳定
 *
 * 适用场景：适用于数据量不大，对稳定性有要求的情况，尤其当数据局部或者整体有序时，采用插入排序可以明显减少数据移动次数，进而提升排序效率。（例如在jdk Arrays.Algorithm.sort()源码中当数组长度小于47时会优先使用插排）
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] A = new int[]{5,6,1,2,3,6,9};
        insertSort2(A);
        System.out.println(Arrays.toString(A));
    }

    static void insertSort(int[] A) {
        for(int i = 1;i < A.length;i++) {
            if(A[i] < A[i-1]) {
                int temp = A[i];
                //所有大于temp的元素向后挪位
                int j = i-1;
                for(;j >= 0 && A[j] > temp;j--) {
                    A[j + 1] = A[j];
                }
                A[j + 1] = temp; //将A[i]复制到插入位置
            }
        }
    }

    static void insertSort2(int[] A) {
        int i, j, low, high, mid;
        for (i = 1;i < A.length;i++) {
            low = 0;high = i-1;
            while(low <= high) {
                mid = (low + high)/2; //向下取整
                if(A[mid] > A[i]) {
                    high = mid - 1; //查找左半子表
                } else
                    low = mid + 1;  //查找右半子表
            }
            int temp = A[i];
            for(j = i-1;j >= low;j--)
                A[j+1] = A[j];
            A[low] = temp;
        }
    }
}
